Data communication networks may include various routers, switches, bridges, and other network devices, coupled to and configured to pass data to one another. These devices will be referred to herein as “network elements.” Data is communicated through the data communication network by passing Protocol Data Units (PDUs), such as Internet Protocol packets, Ethernet Frames, data cells, segments, or other logical associations of bits/bytes of data, between the network elements by utilizing one or more communication links between the network elements. A particular protocol data unit may be handled by multiple network elements and cross multiple communication links as it travels between its source and its destination over the network.
Compression may be used to reduce the amount of data that must be transmitted on a network. One common form of compression is known as Huffman coding. Although Huffman coding is well known in the art, a brief explanation will be provided to facilitate an understanding of the invention. In Huffman coding, a dataset is first assessed to determine the probability of each symbol occurring. For example, as shown in FIG. 1, assume that a dataset includes five different codes, which are represented by the letters A, B, C, D, and E. The first step will be to determine the respective probability of each letter occurring. In this example, it will be assumed that the probability of A occurring is 0.11, B=0.38, C=0.10, D=0.33, and E=0.08. Each of these letters will be assumed to be a symbol. Note, in this example, the sum of the probabilities of the letters equals 1.00.
The Huffman algorithm uses the symbol probabilities to form a Huffman tree 60 as shown in FIG. 1. Specifically, the Huffman code will find the two symbols with the smallest probability and combine them into a new symbol. The new symbol will represent both symbols and have the sum of the probabilities of the two symbols. In this example, symbols E and C have the two lowest probabilities. Thus, a new symbol will be created EC which has a probability of 0.18. This process will be repeated for each symbol (including the newly created symbols such as symbol EC). Thus, for example, once the new symbol EC has been created with a probability of 0.18, the two symbols with the lowest probability will be selected and combined. In this instance, symbol A has probability 0.11 and symbol EC has a probability 0.18. These symbols will be combined to create a new symbol AEC with a probability of 0.29. This process continues combining symbols to form a tree as shown in FIG. 1.
Within the tree, by convention, each time the tree branches the left branch will be assigned a 1, and the right branch will be assigned a 0. The code for a particular symbol is thus the combination of 1s and 0s that is required to traverse the tree to reach the symbol. In the tree of FIG. 1, symbol A has a code “100”, symbol B has a code “0”; symbol C has a code “1011”; symbol D has code “11”; and symbol E has code “1010”. Each code uniquely defines a particular letter. The symbols can have different code lengths, as well, since a particular bit pattern will terminate uniquely on one leaf of the tree. Accordingly, more frequently used symbols may be encoded using fewer bits to thus reduce the size of the data that must be transmitted.
To optimize encoding of a particular dataset, the transmitter will scan the dataset to determine the relative probabilities of the symbols occurring in the dataset. This allows the optimum tree to be created for that dataset so that the compression algorithm compresses the dataset in an optimal fashion. To enable the dataset to be decoded, the transmitter transmits a dictionary describing the codes used for the symbols included in the dataset along with the compressed data. The dictionary describes the symbols and probabilities so that the decoder can form a Huffman tree to decode the data contained in the payload. By transmitting a dictionary that is specific to the dataset, the payload may be encoded optimally. The receiver uses the dictionary to build the Huffman tree, and then can use the tree to decode the compressed data. This is commonly referred to as a static Huffman compression process.
Another way that Huffman coding may be implemented is to have the Huffman tree created without transmission of the dictionary. This process requires the encoder to transmit a specific code commonly referred to as a Not Yet Transmitted (NYT) code. When a decoder sees a NYT code, it recognizes that a new symbol is being transmitted to be added to its Huffman tree. In this way the encoder and decoder may build Huffman trees as symbols are encountered. The inclusion of NYT codes in the encoded output, like inclusion of a dictionary, contributes overhead to the compression process. This is commonly referred to as an adaptive Huffman compression process.
Huffman coding works generally for large datasets because, as the size of the dataset increases, the amount of overhead associated with the dictionary becomes comparatively low. Unfortunately, for small datasets, the overhead associated with the compression dictionary may outweigh the benefits obtained from compression, because the combined size of the compressed dataset plus dictionary may be larger than the original size of the uncompressed dataset.
Thus, Huffman coding compresses better with larger sized datasets. However, as the size of the dataset increases, the processing time required to process the dataset also increases. In communication systems and networks, a longer processing time means longer network delay. For example, as described above, since the static Huffman process is required to first scan the dataset to determine the relative probability of each symbol occurring, increasing the size of the dataset increases the amount of data that must be scanned and also results in a more optimized Huffman tree. Although there are adaptive Huffman encoding methods that may eliminate the initial scanning step and allow the Huffman tree to be built over time, as the dataset increases in size, the overall amount of time it takes to rebuild the Huffman tree for each symbol may slow the compression process. In either instance, where it is desirable to encode data in real time, such as where the encoding process is to be used on time sensitive network traffic or other time sensitive data transfers, reducing the Huffman coding time may be equally as important as compressing network data.
As noted above, communication networks generally include network elements that transmit protocol data units between each other. The protocol data units may vary in size depending on the particular types of protocols being used by the network elements to exchange data. A normal Ethernet frame may have a data size from 46 to 1500 bytes. A jumbo Ethernet frame may have a big data size such as 9000 bytes. An IP packet may carry a TCP segment up to 64 KB, but it is not uncommon for IP packets to be on the order of 250 bytes.
Unfortunately, because of the overhead associated with Huffman coding, Huffman coding often does not work well for compression of small sized network packets. For example, assume that an IP packet has a fixed symbol size of one byte (8 bits). Thus, the packet has potentially 256 symbols. If every symbol occurs at least once, the dictionary size will be 256+bytes. If the IP packet is 1024 bytes long, the impact of the dictionary on the overall compressed packet is 25% (256/1024). Assuming an MTU of 1500 bytes, the dictionary impact on the largest size packet will be 256/1500 or approximately 17%. Depending on the compressibility of the data, this overhead may significantly reduce the effectiveness of the compression process, possibly rendering the overall length of the compressed data larger than the original length of the data.
Additionally, for larger datasets, such as Transmission Control Protocol (TCP) protocol data units and other types of larger protocol data units such as jumbo frames using traditional Huffman coding may require significant processing time on a dedicated processor. While delays of this nature may be tolerable in certain instances, in other instances where the transmission is time sensitive the delay associated with compression using standard Huffman coding may prevent the dataset from being compressed for transmission across the network. Accordingly, although it would be advantageous to compress data for transmission on the network, conventional Huffman coding often is not suitable for compressing small datasets due to excessive overhead, or for compressing large datasets because of the relatively large amount of processing time required to compress the large datasets using the standard Huffman coding process.